package algorithm.leetcode.I1to100;

/**
 * 思路:自定义的快速排序
 * 发现一个严重问题: 利用位运算进行交换,交换的两个位置索引一定不能相同否则会有bug
 * 而快速排序正好就有一样的索引交换操作
 * 结论:交换保证a和b不同可以用异或符,否则老老实实用临时变量
 */

public class Q75 {

    public void sortColors(int[] nums) {
        quickSortColors(nums, 0, nums.length-1);
    }

    private void quickSortColors(int[] nums, int begin, int end) {
        if (begin < end) {
            int pivot = findPivot(nums, begin, end);
            quickSortColors(nums, begin, pivot-1);
            quickSortColors(nums, pivot+1, end);
        }
    }

    private int findPivot(int[] nums, int begin, int end) {
        while (begin < end) {
            while (begin < end && nums[begin] <= nums[end]) end--;
            if (begin < end) swapInPlace(nums, begin, end);
            while (begin < end && nums[begin] <= nums[end]) begin++;
            if (begin < end) swapInPlace(nums, begin, end);
        }
        return begin;
    }

    private static void swapInPlace(int[] nums, int a, int b) {
        nums[a] ^= nums[b];
        nums[b] ^= nums[a];
        nums[a] ^= nums[b];
    }

    public static void main(String[] args) {
        Q75 q75 = new Q75();
        q75.sortColors(new int[]{2,0,2,1,1,0});
    }
}
